#define _CRT_SECURE_NO_WARNINGS   1

//typedef char StackType;
//typedef struct Stack {
//    StackType* a;
//    int top;
//    int capacity;
//}Stack;
//
//void StackInit(Stack* st) {
//    st->a = NULL;
//    st->top = 0;
//    st->capacity = 0;
//
//}
//void StackInsert(Stack* st, StackType val)
//{
//    if (st->top == st->capacity)
//    {
//        int newcapacity = st->capacity == 0 ? 4 : 2 * st->capacity;
//        st->a = (StackType*)realloc(st->a, newcapacity * sizeof(StackType));
//        st->capacity = newcapacity;
//
//    }
//    st->a[st->top++] = val;
//}
//
//void StackPop(Stack* st)
//{
//    if (st->top > 0)
//        st->top--;
//
//
//}
//bool StackEmpty(Stack* st)
//{
//    return st->top == 0;;
//
//}
//
//
//
//
//bool isValid(char* s) {
//    Stack st;
//    StackInit(&st);
//    while (*s)
//    {
//        if (*s == '(' || *s == '{' || *s == '[')
//        {
//            StackInsert(&st, *s);
//            s++;
//        }
//        else if (StackEmpty(&st))
//            return false;
//        else if (st.a[st.top - 1] == '(' && *s != ')' || st.a[st.top - 1] == '[' && *s != ']' || st.a[st.top - 1] == '{' && *s != '}')
//            return false;
//        else
//        {
//            s++;
//            StackPop(&st);
//        }
//
//
//
//    }
//    if (!StackEmpty(&st))
//    {
//        return false;
//    }
//    if (st.capacity != 0)
//    {
//        free(st.a);
//    }
//    return true;
//
//
//}